"""
数独是一个9x9的网格，被分成9个小的3x3的网格。目标是填充网格，使每行、每列和每个3x3网格都包含1到9的数字，且没有重复。
"""
"""
1.从一个空的数独网格开始。
2.在网格中找到一个空的单元格。
3.尝试在该单元格中放置1到9的所有数字。
4.如果数字有效（即不违反任何数独规则），则移动到下一个空的单元格并重复步骤3。
5.如果数字无效，则尝试下一个数字。
6.如果所有数字都已尝试且没有一个有效，则回溯到上一个单元格并尝试下一个数字。
7.重复步骤3到6，直到整个网格都被填满。
"""
import numpy as np


def isValid(grid, row, col, num):
    for i in range(9):
        if grid[row][i] == num:
            return False
        if grid[i][col] == num:
            return False
        if grid[3 * (row // 3) + i // 3][3 * (col // 3) + i % 3] == num:
            return False
    return True


def solveSudoku(grid):
    for i in range(9):  # 行
        for j in range(9):  # 列
            if grid[i][j] == 0:  # 判断该单元格是否为0，如果为0进行操作
                for k in range(1, 10):  # 填充的数 1-9
                    if isValid(grid, i, j, k):
                        grid[i][j] = k
                        if solveSudoku(grid):
                            return True
                        grid[i][j] = 0
                return False
    return True

"""
solveSudoku函数接受一个9x9的网格作为输入，并在数独可解时返回True，否则返回False。
它使用嵌套循环来迭代网格中的所有单元格。
    如果一个单元格为空（即其值为0），它使用另一个循环尝试在该单元格中放置1到9的所有数字。
        如果数字有效（即不违反任何数独规则），则移动到下一个空的单元格并重复该过程。
        如果数字无效，则尝试下一个数字。
        如果所有数字都已尝试且没有一个有效，则回溯到上一个单元格并尝试下一个数字。


isValid函数通过检查数字是否违反任何数独规则（即是否已经存在于同一行、列或3x3网格中）来检查数字是否有效。
"""

chessboard = np.array([[0] * 9 for _ in range(9)])
solveSudoku(chessboard)
print(chessboard)
